/**
 * 
 */
package it.uniroma3.dia.digraph.algorithm.kouterplanar.outerplanar;

import it.uniroma3.dia.digraph.algorithm.Algorithm;
import it.uniroma3.dia.digraph.algorithm.utility.Utility;
import it.uniroma3.dia.digraph.algorithm.utility.kouterplanar.Peeler;
import it.uniroma3.dia.digraph.algorithm.utility.kouterplanar.outerplanar.OuterplanarGraph;
import it.uniroma3.dia.digraph.algorithm.utility.kouterplanar.outerplanar.OuterplanarNode;

import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.graphdrawing.graphml.xmlns.GraphType;
import org.graphdrawing.graphml.xmlns.NodeType;

/**
 * Target: move the node of the graph to form a convex shape.
 * 
 * for i=1....i=|V|-2:
 * 
 * 	Choose 1 node: it has to be not yet visited and its considered degree must be 2.
 * 	Find its previous and next not yet visited node.
 * 	Determine an admissible radius for the circumference passing through "previous" and "next" nodes.
 * 	Move all nodes among previous and next on the circumference.
 *  
 * @author Cionzo
 *
 */
public class MakeConvex extends Algorithm {

	private OuterplanarGraph outGraph;
	private List<OuterplanarNode> outNodeList;
	private List<NodeType> movingNodes;
	private Map<String, Boolean> visitMap;
	
//	private NodeType vertex, c, d;
	
	private OuterplanarNode previous, current, next;
	NodeType currentCenter;
	private Point2D.Double top;

	/* (non-Javadoc)
	 * @see it.uniroma3.dia.digraph.algorithm.Algorithm#apply(org.graphdrawing.graphml.xmlns.GraphType[])
	 */
	@Override
	public void apply(GraphType... inputGraphs) {		
			
		Point2D.Double center = null;
		this.top = new Point2D.Double();

		//find current, previous and next		
		this.findCurrPrevNext();
		
		
		//while there is a node to move and both its previous and its next are not null 
		while (this.current!=null && this.previous!=null && this.next!=null){
			
			this.movingNodes = getMovingNodes(previous, next);
			
			//define the circumference where the nodes will be moved
			center = this.findCenter();				
			
			//move the nodes
			this.moveNodes(center);

			//show what's up
			this.showView();			

			//update current selected nodes condition (decrement degree, mark as visited)
			this.updateCondition();

			//search for three new vertices
			this.findCurrPrevNext();
		}

	}


	/**
	 * Builds a list containing the nodes to check to preserve planarity during the current step.
	 * The list will contain all graph nodes except those on the path morphed during the current step.
	 * @return a list containing the nodes to check to preserve planarity during the current step.
	 */
	private List<NodeType> buildCheckNodeList() {
		List<NodeType>nodes = this.getMovingNodes(this.previous, this.next);
		List<NodeType> nodesToCheck = new LinkedList<NodeType>(this.graph.getNodeCollection().getNode());
		nodesToCheck.removeAll(nodes);
		return nodesToCheck;
	}

	
	/**
	 * Calculates the angle for the third vertex of an isosceles triangle whose base is the segment "previous"-"next".
	 * The vertex must lie in the outer face, so the angle must be chosen correctly.
	 * @param middle segment "previous"-"next" midpoint
	 * @return the angle (in degrees) -respect to "middle"- that must be described by the third vertex of the triangle.   
	 */
	private double calculateTheta(Point2D.Double middle) {		
		double theta, prevTheta, currTheta, nextTheta;
		
		prevTheta = Utility.getAngle(middle, previous.getNode());
		currTheta = Utility.getAngle(middle, current.getNode());
		nextTheta = Utility.getAngle(middle, next.getNode());

		theta = 0.5*prevTheta + 0.5*nextTheta;
		
		if (!(Math.min(prevTheta, nextTheta)< currTheta && currTheta< Math.max(prevTheta, nextTheta)))
			theta += 180;			
		
		theta = theta % 360;	
		
		
		return theta;
	}

	
	/**
	 * If the circumcenter lies in the triangle, chose its symmetrical point using segment "previous"-"next" as symmetry axis.
	 * @param center triangle previous-next-top circumcenter 
	 */
	private void moveCircumCenterOutSideTriangle(Point2D.Double center) {
		double dist;
		double[] coords;
		Point2D.Double mid;
		
		//if the circumcenter lies internally to the triangle,
		//use segment "previous"-"next" as symmetry axis		
		if (isCenterInside(center)){			
			
			mid = Utility.midpoint(this.previous.getNode(), this.next.getNode());
			double alpha = Utility.getAngle(mid, this.top.x, this.top.y);
			alpha +=180;
			alpha = alpha%360;
			dist = Utility.distance(mid, this.top);
			coords = Utility.convertToCartesianCoords(mid, alpha, dist);
			center.setLocation(coords[0], coords[1]);
		}		
	}


	/* (non-Javadoc)
	 * @see it.uniroma3.dia.digraph.algorithm.Algorithm#checkInput(org.graphdrawing.graphml.xmlns.GraphType[])
	 */
	@Override
	public void checkInput(GraphType[] inputGraphs)
	throws InputMismatchException {
		if (inputGraphs.length!=1 || 
				Peeler.decomposeToLayers(inputGraphs[0]).size()!=1)
			throw new InputMismatchException("input graph must be a 1-outerplanar graph");
	}


	/**
	 * Calculates the center of the circumference where the nodes will be moved during current step. 
	 * @return a point representing the center of the circumference where the nodes will be moved during current step.
	 */
	private Point2D.Double findCenter() {
		
		this.top = this.findVertex();		
		
		Point2D.Double center = Utility.getCircumCenter(
				this.previous.getNode(), 
				top, 
				this.next.getNode());		
		
		this.moveCircumCenterOutSideTriangle(center);
		return center;
		
	}

	/**
	 * Finds the nodes to be considered as the current and its previous and next during the current step.
	 */
	private void findCurrPrevNext() {
		this.current = this.findNotYetVisitedNode();		
		this.previous = this.findPrevious();
		this.next = this.findNext();
	}


	/**
	 * Search for the node to be considered the next (in the current step) for the
	 * node "current", 
	 * @param current
	 * @param previous
	 * @return
	 */
	private OuterplanarNode findNext(){
		int size = this.outNodeList.size();
		int cIndex = this.outNodeList.indexOf(this.current);
		int pIndex = this.outNodeList.indexOf(this.previous);
		int nIndex = cIndex + 1;
		OuterplanarNode next;

		while ( (nIndex % size)!=pIndex){
			next = this.outNodeList.get(nIndex % size);
//						System.out.println("try to get "+next+" as next for "+current);
			if (!this.visitMap.get(next.getId())){
//								System.out.println("chosen "+next+" as previous for "+current);
				return next;			
			}
			nIndex++;
		}
		return null;
	}


	/**
	 * Finds a (not yet visited) node with (considered) degree equals to 2 in the considered graph.
	 * @return the first outerplanar node with degree equals to 2 if exists, null otherwise 
	 * @see {@link OuterplanarNode#getConsideredDegree()}
	 */
	private OuterplanarNode findNotYetVisitedNode(){

		for (OuterplanarNode node : this.outNodeList)
			if (!this.visitMap.get(node.getId()) && node.getConsideredDegree()==2)
				return node;

		return null;
	}



	/**
	 * Search for a node to be considered the previous for the "current" node in this step
	 * @param current
	 * @return
	 */
	private OuterplanarNode findPrevious(){
		int size = this.outNodeList.size();
		int cIndex = this.outNodeList.indexOf(this.current);
		int pIndex = cIndex + size -1;

		OuterplanarNode prev;
		while (pIndex>cIndex){
			prev = this.outNodeList.get(pIndex % size);
//						System.out.println("try to get "+prev+" as previous for "+current);
			if (!this.visitMap.get(prev.getId())){
//								System.out.println("chosen "+prev+" as previous for "+current);
				return prev;
			}
			pIndex--;
		}

		return null;
	}





	/**
	 * Finds the vertex of the triangle where nodes have to be put
	 * @return a point representing the vertex of the triangle where the nodes have to be put
	 */
	private Point2D.Double findVertex() {
		
		Point2D.Double mid;		
		double theta, height;
		Point2D.Double[] boxVertices;		
		
		mid = Utility.midpoint(this.previous.getNode(), this.next.getNode());
		theta = this.calculateTheta(mid);
		height = Utility.distance(this.current.getNode(), mid);		
		
		boxVertices = Utility.findBoxVertices(this.previous.getNode(), this.next.getNode(), height, theta);		
		List<NodeType> nodesToCheck = buildCheckNodeList();
				
		//decrease box height until it isn't spannable
		while (!Utility.isSpannablePolygon(boxVertices, nodesToCheck, this.edgeList, this.idToNodes)){
			height = height * 0.75;
			System.out.println("spanning box is not empty: try h="+height);
			boxVertices = Utility.findBoxVertices(this.previous.getNode(), this.next.getNode(), height, theta);	
		}
		
		mid = Utility.midpoint(boxVertices[2], boxVertices[3]);
		this.top.setLocation(mid.x, mid.y);
		return mid;
	}


	/**
	 * Builds a list containing the path chosen for this step.
	 * Returned list is a sublist of that representing the boundary.
	 * Boundary list must be ordered representing a boundary walk.
	 * @param first the first node to include in the list
	 * @param last the last node to include in the list
	 * @return a list containing the path chosen for this step
	 */
	private List<NodeType> getMovingNodes(OuterplanarNode first,
			OuterplanarNode last) {
		
		List<NodeType> list = new LinkedList<NodeType>();
		int ip = this.outNodeList.indexOf(first);
		int in = this.outNodeList.indexOf(last);
		boolean stop = false;
		int i = ip;
		int size = this.outNodeList.size();
		
		while (!stop){
			list.add(this.outNodeList.get(i%size).getNode());	
			
			if ((i%size)==in)
				stop = true;
			i++;
		}		
		return list;
	}



	/* (non-Javadoc)
	 * @see it.uniroma3.dia.digraph.algorithm.Algorithm#init(org.graphdrawing.graphml.xmlns.GraphType[])
	 */
	@Override
	protected void init(GraphType... inputGraphs) {	

		//custom init
		this.outGraph = new OuterplanarGraph(this.graph);
		this.outNodeList = this.outGraph.getNodes();  
		this.visitMap = this.initVisitMap();

	}

	/**
	 * Initializes the visit map for the nodes of the considered graph 
	 * @return a map node->false
	 */
	private Map<String, Boolean> initVisitMap() {
		Map<String, Boolean> map = new HashMap<String, Boolean>();

		for (OuterplanarNode on : this.outNodeList)
			map.put(on.getId(), false);

		return map;
	}

	/**
	 * Checks whether circumcenter of the triangle "previous"-"next"-"top" 
	 * lies inside the triangle. 
	 * @param center the point representing the circumcenter of the triangle.
	 * @return true if the point lies in the triangle, false otherwise.
	 */
	private boolean isCenterInside(Point2D.Double center) {
		double[] coords = Utility.barycentricCoords(center, previous.getNode(), next.getNode(), top);
		
		for (double c : coords){
//			System.out.println(c);
			if (c>=1 || c<0)
				return false;
		}
		return true;
	}

	/**
	 * Moves the nodes between "previous" and "next" on a circumference arc.
	 * The circumference is centered in "center" and has radius "radius"
	 * @param center the center of the circumference
	 * @param previous the first considered node in this step
	 * @param next the last considered node in this step
	 */
	private void moveNodes(Double center) {
		
		NodeType movingNode;
		double theta, fx, fy, lx,ly, x, y;
		double[] coords;
		double percent, remaining;
		double step = 1.0/(this.movingNodes.size()-1);		
		
		fx = this.movingNodes.get(0).getX();
		fy = this.movingNodes.get(0).getY();
		lx = this.movingNodes.get(this.movingNodes.size()-1).getX();
		ly = this.movingNodes.get(this.movingNodes.size()-1).getY();
		
		double distBla = Utility.distance(this.movingNodes.get(0), center);
		
		//for each node from previous to next		
		for (int i=1;i<this.movingNodes.size()-1;i++){
			percent = i*step;
			remaining = 1-percent;
			
			//find a point as combination of previous and next
			x = percent*lx + remaining*fx;
			y = percent*ly + remaining*fy;			
			
			//consider its projection on the circumference
			theta = Utility.getAngle(center.x, center.y, x, y);			
			coords = Utility.convertToCartesianCoords(center, theta, distBla);
			
			//move the current node to the found location
			movingNode = this.movingNodes.get(i);			
			movingNode.setX(coords[0]);
			movingNode.setY(coords[1]);
			
		}
	}

	/**
	 * Changes the "default" value attribute for the specified nodes
	 * @param value the value to be set to the default attribute of each node in the list
	 * @param nodes the nodes to change default attribute
	 */
	private void setDefaultValue(boolean value, OuterplanarNode... nodes) {
		NodeType[] nts = new NodeType[nodes.length]; 
		for (int i=0;i<nts.length;i++)
			nts[i] = nodes[i].getNode();

		Utility.setDefalut(value, nts);
	}

	/**
	 * Update the view about the changes occurred in the current step
	 */
	private void showView() {
		this.setDefaultValue(false, previous, current, next);
		this.updateView();
		this.setDefaultValue(true, previous, current, next);
		
	}


	/**
	 * Updates condition for the specified nodes
	 * @param previous
	 * @param current
	 * @param next
	 */
	private void updateCondition() {

		previous.decreaseConsideredDegree();
		next.decreaseConsideredDegree();
		this.visitMap.put(current.getId(), true);

	}

}
